// https://leetcode.cn/problems/missing-two-lcci/description/

// 算法思路总结：
// 1. 使用异或运算找出两个缺失数字的异或结果
// 2. 通过最低有效位将数字分为两组
// 3. 分别对两组数字进行异或操作找出两个缺失数
// 4. 时间复杂度：O(n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>

class Solution 
{
public:
    vector<int> missingTwo(vector<int>& nums) 
    {
        // N - 2个数
        int n = nums.size();

        // 求出 a ^ b
        int sum = 0;
        for (int i = 0 ; i < n ; i++)
            sum ^= nums[i];

        for (int i = 1 ; i <= n + 2 ; i++)
            sum ^= i;

        // 找出区分比特位
        int diff = 0;
        while (1)
        {
            if ((sum >> diff) & 1)
                break;
            else diff++;
        }

        // 分组异或，求出答案
        int a = 0, b = 0;
        for (int i = 0 ; i < n ; i++)
        {
            if ((nums[i] >> diff) & 1)
                a ^= nums[i];
            else b ^= nums[i];
        }

        for (int i = 1 ; i <= n + 2 ; i++)
        {
            if ((i >> diff) & 1)
                a ^= i;
            else b ^= i;
        }
        return {a, b};
    }
};

int main()
{
    vector<int> v1 = {1}, v2 = {2, 3};
    Solution sol;

    auto r1 = sol.missingTwo(v1), r2 = sol.missingTwo(v2);

    for (auto& num : r1) 
        cout << num << " ";
    cout << endl;

    for (auto& num : r2)
        cout << num << " ";
    cout << endl;

    return 0;
}